﻿using System;
using System.Collections.Generic;
using System.Drawing;

namespace path
{
    class Program
    {
        const int N = 10;
        const int BUSY = 5;
        const int FREE = 0;
        const int VISITED = 1;
        const int DEADLOCK = 2;
        static byte[,] matr = new byte[N,N];
        static Point p = new Point(9, 0);
        static Stack<Point> history = new Stack<Point>();

        static void MatrOut()
        {
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                    Console.Write(matr[i, j].ToString() + " ");
                Console.WriteLine();
            }   
        }
        static void SetMatr()
        {
            matr[6, 0] = BUSY;
            matr[7, 0] = BUSY;
            matr[8, 0] = BUSY;
            matr[8, 1] = BUSY;
            matr[8, 3] = BUSY;
            matr[9, 3] = BUSY;
            matr[5, 0] = BUSY;
            matr[5, 1] = BUSY;
            matr[5, 2] = BUSY;
            matr[5, 3] = BUSY;
            matr[7, 3] = BUSY;

        }
        static void GoTo(Point dest)
        {
            matr[p.X, p.Y] = VISITED;
            if (p != dest)
            {
                if (p.X > 0 && matr[p.X - 1, p.Y] != BUSY && matr[p.X - 1, p.Y] != VISITED && matr[p.X - 1, p.Y] != DEADLOCK)
                {
                    history.Push(new Point(p.X, p.Y));
                    p.X--;
                    GoTo(dest);                    
                }
                else
                    if (p.X < N - 1 && matr[p.X + 1, p.Y] != BUSY && matr[p.X + 1, p.Y] != VISITED && matr[p.X + 1, p.Y] != DEADLOCK)
                    {
                        history.Push(new Point(p.X, p.Y));
                        p.X++;
                        GoTo(dest);
                    }
                    else
                        if (p.Y > 0 && matr[p.X, p.Y - 1] != BUSY && matr[p.X, p.Y - 1] != VISITED && matr[p.X, p.Y - 1] != DEADLOCK)
                        {
                            history.Push(new Point(p.X, p.Y));
                            p.Y--;
                            GoTo(dest);
                        }
                        else
                            if (p.Y < N - 1 && matr[p.X, p.Y + 1] != BUSY && matr[p.X, p.Y + 1] != VISITED && matr[p.X, p.Y + 1] != DEADLOCK)
                            {
                                history.Push(new Point(p.X, p.Y));
                                p.Y++;
                                GoTo(dest);
                            }
                            else
                            {
                                matr[p.X, p.Y] = DEADLOCK;
                                p = history.Pop();
                            }
            }
            return; 
        }


        static void Main(string[] args)
        {
            SetMatr();
            GoTo(new Point(6,4));
            MatrOut();
            Console.ReadLine();
        }
    }
}
